
\section{Conclusion}
\label{sec:game.discussion}

Non-cooperative games have been recognized as a useful paradigm for
studying decentralized network security problems; however, the
resources needed for individual decision making are important issues
for the implementability of such games.  In this paper, we have
developed a framework for network security games parametrized by the
amount of local information available for individual decision
making. We find this parameter plays an important role in the
structure of the equilibria, and needs to be taken into account in
such analysis.

NE are considered as natural operating configurations in such systems
with selfish users.  Therefore, ensuring that the system has efficient
NE is desirable (equivalently, a low price of anarchy (PoA)) for
network planners.  Specifically, if the network planner has a limited
budget to secure $k$ nodes, an important design problem is to choose a
subset of nodes to secure so that the graph restricted to the
remaining nodes has low PoA; such a strategy is also referred to as a
\emph{Stackelberg} strategy for the network planner \cite{nisan:book}.
Lemmas \ref{lemma:game.poa-d1} and \ref{lemma:game.poa-dinfty}, which bound the
PoA in terms of the network parameters, suggest natural heuristics to
design stackelberg strategies for the network planner. We discuss this
briefly below.

In the neighborhood model, Lemma \ref{lemma:game.poa-d1} shows that PoA is
bounded by $\Delta+1$. Therefore, given a budget to secure $k$ nodes,
the Stackelberg question is to choose a subset of nodes to secure, so
that the maximum degree of the residual graph is minimized. An
analogous question, dual to this, is the following: for a given target
maximum degree $\Delta'$, choose the smallest set $k$ of nodes to
secure so that the maximum degree in the residual graph is
$\Delta'$. Both these versions are NP-complete to solve optimally, but
greedy heuristics are likely to perform well. In the global model,
Lemma \ref{lemma:game.poa-dinfty} shows that the PoA is bounded by
$1/\alpha(\mathcal{G})$. The analogous question of finding an optimal
Stackelberg strategy is NP-complete in this case also. We can use the
spectral clustering algorithm of \cite{kannan:spectral}, which finds
an $(\alpha,\epsilon)$ clustering of low cost using at most an
$\epsilon$ fraction of the edges, while ensuring that each cluster has
expansion at least $\alpha$, as a natural heuristic for this problem.

\junk{ Finally, there are a number of other possible infection models
  which are interesting, and could be more useful in specific
  settings. We mention two of them here. In the first model, we modify
  the infection model so that $i$ infects $j$ if they are within
  distance $d$ in the original graph $\mathcal{G}$, and remain
  connected in ${\mathcal{G}}[\vec{a}]$ - this models settings in
  which even secure nodes can spread the infection, though they
  themselves cannot get infected. In the second model, we have a
  probability for disease transmission on each edge, which captures
  SIS/SIR worm propagation models. Other extensions of our models
  include directed and weighted graphs.  Many of our results,
  especially the lower bounds, extend to these models as well, though
  they present new challenges.  }
